'''
nums: [1, 2, 3, 4, 5, 7]
ops:  [+, +, -, +, -, +]
'''


def push(nums, ops, num, op):
    # 如果前一个是乘除，先计算
    if ops and ops[-1] in {'*', '/'}:
        nums[-1] = nums[-1] * num if ops[-1] == '*' else nums[-1] / num
        ops[-1] = op
    else:
        nums.append(num)
        ops.append(op)


def compute(nums, ops):
    n = len(nums)
    ans = nums[0]
    for i in range(1, n):
        ans += nums[i] if ops[i - 1] == '+' else -nums[i]
    return ans


def calculate(s: str) -> int:
    where = 0
    n = len(s)
    operation_set = {'+', '-', '*', '/'}
    digit_set = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}

    def process(i):
        nonlocal where
        cur = 0
        nums = []
        ops = []
        # 一个子括号内的计算栈，或者最外层的计算栈
        while i < n and s[i] != ')':
            if s[i] in digit_set:
                cur = cur * 10 + int(s[i])
            elif s[i] in operation_set:
                push(nums, ops, cur, s[i])
                cur = 0  # 重置cur
            else:
                # 左括号
                cur = process(i + 1)
                i = where
            i += 1
        where = i
        push(nums, ops, cur, '+')
        return compute(nums, ops)

    return process(0)


if __name__ == "__main__":
    # v = 36-(4*(3+2*(1-6))+5)+17
    # s = '36-(4*(3+2*(1-6))+5)+17'
    v = 312 + (123 + 12 * (13) - 123 + 2 * (98 + (22 - 123 * (1 + (23 - 28) - 9) - 5) - 2)) * 100 + 2
    s = '312 + (123 + 12 * (13) - 123 + 2 * (98 + (22 - 123 * (1 + (23 - 28) - 9) - 5) - 2)) * 100 + 2'.split(' ')
    s = ''.join(s)
    print(calculate(s))
    print(v)
